package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/16 10:25
 * @description:  最长回文子串
 */
public class LongersPalindrome {

    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        String s = sr.nextLine();
        System.out.println(new LonersPalindrome_Solution().longestPalindrome1(s));
        System.out.println(new LonersPalindrome_Solution().longestPalindrome2(s));
    }
}

class LonersPalindrome_Solution{
    public String longestPalindrome1(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for(int i =0;i < len;i++){
            for(int j =i+1;j<=len;j++){
                String sub = s.substring(i,j);
                if(is_palindrome(sub) && sub.length() >max){
                    ans = sub;
                    max = sub.length();
                }
            }
        }
        return ans;
    }


    public boolean is_palindrome(String s){

        int len = s.length();
        int start = 0,end = len-1;
        while(start <= end){
            if(s.charAt(start++) != s.charAt(end--)){
                return false;
            }
        }
        return true;
    }


    public String longestPalindrome2(String s){


        int len = s.length();
        //定义dp[i][j]  为字符串i~j是否为回文字符串
        boolean [][]dp = new boolean[len][len];
        for(int i = 0;i < len;i++){
            dp[i][i] = true;
        }
        int L,max =0,start =0,end =0;

        //枚举字符串长度,从2开始，长度为1的已经初始化为true
        for(L =2 ;L <=len; L++){
            //左边界
            for(int i = 0;i < len;i++){
                int j = i+L-1;
                if(j >= len){
                    break;
                }
                //左边界和右边界不相等 则不是回文
                if(s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    if(L <= 3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];  //因为字符串长度的枚举是从低->高的，所以dp[i+1][j-1]已经确定true or false了
                    }
                }

                if(dp[i][j] && L > max){
                    max = L;
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start,end+1);
    }
}